#include "pch.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Djj(vector<vector<int>>&vec,vector<int>&result,int v0) {

	vector<int> visited(vec.size(),0);
	int last_visited = 0;
	visited[v0] = 1;
	result[0] = 0;
	for (int i = 0; i < vec.size(); i++) {
		for (int j = 0; j < vec.size(); j++) {
			if (visited[j] == 0 && vec[v0][j] != 0) {
				//int dist = vec[v0][j] + last_visited;
				//if (dist < result[j]) result[j] = dist;
				result[j] = min(result[j],vec[v0][j]+last_visited);
			}
		}
		int minIndex = 0;
		//while (visited[minIndex] == 1) minIndex++;//找到第一个没有被选中的节点
		for (int j = 0; j < vec.size(); j++) {
			if (visited[j] == 0 && result[j] < result[minIndex]) {
				minIndex = j;
			}
		}
		last_visited = result[minIndex];
		visited[minIndex] = 1;
		v0 = minIndex;
	}

}




class Solution {
public:
    void Dijkstra(vector<vector<int>>& graph, vector<int>& distances, vector<bool>& visited, int n, int distanceThreshold, int start) {
        distances[start] = 0; //自身到自身的距离为0
        for (int i=0; i<n; ++i) {
            int u=-1, minDis = INT_MAX;
            for (int j=0; j<n; ++j) {
                if (!visited[j] && distances[j] < minDis) {
                    u = j;
                    minDis = distances[j];
                }
            }
            if (u==-1) return; //所有点不可达
            visited[u] = true;
            for (int v=0; v<n; ++v) {
                if (!visited[v] && graph[u][v] != INT_MAX) {
                    if (distances[u] + graph[u][v] < distances[v]) {
                        distances[v] = distances[u] + graph[u][v];
                    }
                }
            }
        }
    }
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<vector<int>>graph(n,vector<int>(n,INT_MAX)); //邻接矩阵
        for (vector<int> edge : edges) {
            int u=edge[0], v=edge[1], w=edge[2];
            graph[u][v] = graph[v][u] = w;
        }
        int idx = -1, minCount = INT_MAX;
        for (int i=0; i<n; ++i) {
            vector<int>distances(n,INT_MAX); //单源最短路径数组
            vector<bool>visited(n,false);
            Dijkstra(graph, distances, visited, n, distanceThreshold, i);
            int count = 0; //小于等于距离阈值的城市个数
            for (int j=0; j<n; ++j) {
                if (distances[j]<=distanceThreshold && i!=j) {
                    count++;
                }
            }
            if (count <= minCount) {
                minCount = count;
                idx = i;
            }
        }
        return idx;
    }
};
